/*
day72_3
2019.11.8
*/
#include<stdio.h>
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
};


int numTrees(int n){
	long cur1=1;
	
	for(int i=0,start=n ; i<n ; i++)
	{
//		printf("%d\t%d\n",i,start); 
		cur1 *= start;
		start--;
	}
//	printf("\n");
//	printf("%l\n",cur1);
	
	long cur2=1;
	for(int i=0,start=2*n ; i<n ; i++)
	{
//		printf("%d\t%d\n",i,start);
		cur2 *= start;
		start--;
	}
//	printf("\n");
//	printf("%l\n",cur2);
	
	return (int)cur2/cur1/(n+1); 
}

int main()
{
	int num=numTrees(9); 
	printf("%d",num);
	return 0;
}
